<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <link rel="shortcut icon" href="">
    <title>AStar</title>
    <style type="text/css">
        body {
            background-color: #eccc68;
        }

        canvas {
            width: 400px;
            height: 300px;
            border: 1px solid black;
        }
    </style>
</head>

<body>
    <h1>AStar</h1>
    <script type="module">
        import {createCanvas, vector2, animation, mouse, curve, circle, rect, line, fill, stroke, lineWidth, frame, noloop} from './spring/board.js'
        import {Particle, Spring} from './spring/object.js'

        const width = 1200, height = 800, w = 50
        const cols = ~~(width / w), rows = ~~(height / w)
        const openList = [], closeList = [], grid = []

        class Spot {
            constructor(i, j, wall = 0.6) {
                this.i = i
                this.j = j
                this.g = 0
                this.h = 0
                this.f = 0
                this.neighbors = []
                this.previous = null
                this.wall = Math.random() > wall
            }
            show(color) {
                const { i, j, wall } = this
                // rect((i + 0.5) * w, (j + 0.5) * w, w - 1, w - 1)
                circle((i + 0.5) * w, (j + 0.5) * w, (w - 1) / 2, 20)
                fill(wall ? '#000' : color)
            }
            addNeighor(grid) {
                const { i, j, neighbors } = this
                i > 0        && neighbors.push(grid[i - 1][j])
                i < cols - 1 && neighbors.push(grid[i + 1][j])
                j > 0        && neighbors.push(grid[i][j - 1])
                j < rows - 1 && neighbors.push(grid[i][j + 1])
                i > 0 && j > 0        && neighbors.push(grid[i - 1][j - 1])
                i > 0 && j < rows - 1 && neighbors.push(grid[i - 1][j + 1])
                i < cols - 1 && j > 0 && neighbors.push(grid[i + 1][j - 1])
                i < cols - 1 && j < rows - 1 && neighbors.push(grid[i + 1][j + 1])
                /*
                */
            }
        }

        function removeFromArray(array, el) {
            if (array instanceof Array) {
                for (let i = 0; i < array.length; ++i) {
                    if (array[i] === el) {
                        array.splice(i, 1)
                    }
                }
            }
        }

        function heuristic(current, target) {
            // return Math.abs(current.i - target.i) + Math.abs(current.j - target.j)
            return Math.sqrt(Math.pow(current.i - target.i, 2) + Math.pow(current.j - target.j, 2))
        }

        for (let i = 0; i < cols; ++i) {
            grid[i] = []
            for (let j = 0; j < rows; ++j) {
                grid[i][j] = new Spot(i, j)
            }
        }
        for (let i = 0; i < cols; ++i) {
            for (let j = 0; j < rows; ++j) {
                grid[i][j].addNeighor(grid)
            }
        }
        let start = grid[0][0], end = grid[cols - 1][rows - 1]
        let current = start
        start.wall = false
        end.wall = false
        openList.push(start)
        createCanvas(width / 2, height / 2)
        let running = 1
        function draw() {
            let path = []
            if (openList.length > 0 && running > 0) {
                let index = 0
                for (let i = 0; i < openList.length; ++i) {
                    if (openList[i].f < openList[index].f) {
                        index = i
                    }
                }
                current = openList[index]
                removeFromArray(openList, current)
                closeList.push(current)
                if (current === end) {
                    // openList.length = 0
                    running = 0
                    console.log('DONE!')
                    return
                }
                let neighbors = current.neighbors
                for (let i = 0; i < neighbors.length; ++i) {
                    let neighbor =  neighbors[i]
                    // can't run the wall or pass
                    if (!closeList.includes(neighbor) && !neighbor.wall) {
                        let g = current.g + 1
                        if (openList.includes(neighbor)) {
                            if (g < neighbor.g) {
                                neighbor.g = g
                            } else {
                                // do not run this spot
                                continue
                            }
                        } else {
                            neighbor.g = g
                            openList.push(neighbor)
                        }
                        neighbor.h = heuristic(neighbor, end)
                        neighbor.f = neighbor.g + neighbor.h
                        neighbor.previous = current
                    }
                }
            } else {
                if (running > 0) {
                    console.log("no solution")
                    running = -1
                    noloop()
                }
            }

            for (let i = 0; i < cols; ++i) {
                for (let j = 0; j < rows; ++j) {
                    grid[i][j].show()
                }
            }
            for (let item of openList) {
                item.show('rgba(0, 255, 0, .8)')
            }
            for (let item of closeList) {
                item.show('rgba(0, 255, 255, .8)')
            }
            if (running > -1) {
                let temp = current
                while(temp.previous) {
                    path.push(temp)
                    temp = temp.previous
                }
                path.push(start)

                for (let item of path) {
                    item.show('rgba(255, 0, 255, .8)')
                }
                let verties = []
                for (let item of path) {
                    verties.unshift({x: (item.i + .5) * w, y: (item.j + .5) * w})
                }
                lineWidth(5)
                curve(verties, stroke)
            }

        }
        animation(draw)
    </script>
</body>

</html>